package graph;
import java.util.ArrayList;
import java.util.List;
//A*寻路算法简单实现————>四方向（上下左右）
public class Maze_A_ManHaDun {
	
	//简单的迷宫模拟——利用二维数组，其中 1 表示障碍，不可通过。
	public static final int[][] MAZE= {
	{0, 1, 0, 0, 0, 0, 0},//7
	{0, 0, 1, 0, 0, 0, 0},
	{1, 0, 0, 1, 0, 0, 0},
	{0, 1, 0, 1, 1, 1, 1},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 1, 1, 1, 0},
	//7
	};

	
	//定义 方格节点——grid
	static class Grid{
		public int x;//结点
		public int y;
		public int f;//fn
		public int g;//gn
		public int h;//hn
		public Grid parent;
		
		
		public Grid(int x,int y) {
			this.x=x;
			this.y=y;
		}
		
		//实例化一个方格节点
		public void initGrid(Grid parent, Grid end) {
			//parent赋值
			this.parent=parent;
			
			//计算g的大小
			if(parent!=null) {
				this.g=parent.g+1;
				//this.g=0;
			}
			else
			{
				this.g=1;
			}
			
			//计算h的大小
			this.h=Math.abs(this.x-end.x)+Math.abs(this.y-end.y);
			//this.h=Math.abs(this.x-end.x)*Math.abs(this.y-end.y);		
			//计算f的大小
			this.f=this.g+this.h;
		}
	}
	
	//寻路算法核心实现过程
	public static Grid aStarSearch(Grid start, Grid end) {
		
		//准备两个链表，分别存储 将要选择的节点  和  已经走过的节点
		ArrayList<Grid> openlist=new ArrayList<Grid>();
		ArrayList<Grid> closelist=new ArrayList<Grid>();
		
		//将起点加入链表，准备开始寻路。
		openlist.add(start);
		
		//只要链表不为空，就重复这个寻路的过程
		while(openlist.size()>0) {
			
			//找到 openlist中 F值最小的那个 方格（节点）
			Grid currentgrid=findMinGrid(openlist);
			
			//从 openlist中删除找到的那个  F值 最小的那个节点
			openlist.remove(currentgrid);
			
			//将这个  F值 最小的节点，加入到  closelist 中
			closelist.add(currentgrid);
			
			//寻找  当前找到的这个 F值最小的节点的  邻居节点 ——上下左右，四个方向上的节点，要判断它们是否为合法可用的节点。
			List<Grid> neighbors=findNeighbors(currentgrid, openlist, closelist);
			
			//对合法可用的邻居节点进行初始化，并加入到  openlist中
			for(Grid grid : neighbors) {
				if(!openlist.contains(grid)) {
					grid.initGrid(currentgrid,end);
					openlist.add(grid);
				}
			}
			
			//邻居节点加入  openlist 后，判断openlist中，是否包含  终点节点，如果包含终点，直接返回并退出。
			for(Grid grid : openlist) {
				if((grid.x==end.x) && (grid.y==end.y)) {
					return grid;
				}
			}
		}
		
		return null;
	}
	
	
	//寻找邻居节点的方法，返回值为  链表  ——创建一个合理的邻居链表
	private static ArrayList<Grid> findNeighbors(Grid grid, List<Grid> openlist, List<Grid> closelist) {
		// TODO Auto-generated method stub
		
		ArrayList<Grid> gridlist=new ArrayList<Grid>();
		
		//判断上下左右邻居节点的合理性，没问题就加入到邻居链表中。
		if(isValidGrid(grid.x, grid.y-1, openlist, closelist)) {//下
			gridlist.add(new Grid(grid.x, grid.y-1));
		}
		
		if(isValidGrid(grid.x, grid.y+1, openlist, closelist)) {//上
			gridlist.add(new Grid(grid.x, grid.y+1));
		}
		
		if(isValidGrid(grid.x-1, grid.y, openlist, closelist)) {//左
			gridlist.add(new Grid(grid.x-1, grid.y));
		}
		
		if(isValidGrid(grid.x+1, grid.y, openlist, closelist)) {//右
			gridlist.add(new Grid(grid.x+1, grid.y));
		}
		
		
		return gridlist;
	}
 
	//判断当前位置的节点是否合理
	private static boolean isValidGrid(int x, int y, List<Grid> openlist, List<Grid> closelist) {
		// TODO Auto-generated method stub
		
		//当前节点是否越界，不再MAZE数组范围内了，注意二位数组的长度计算方法及含意
		//MAZE。length表示行的长度
		//MAZE[0]。length表示列的长度
		if(x<0 || x>=MAZE.length || y<0 || y>=MAZE[0].length) {
			return false;
		}
		
		//当前节点是否为障碍节点
		if(MAZE[x][y]==1) {
			return false;
		}
		
		
		//判断当前节点是否在 openlist中
		if(containgrid(openlist, x, y)) {
			return false;
		}
		
		//判断当前节点是否在 closelist中
		if(containgrid(closelist, x, y)) {
			return false;
		}
		
		return true;
	}
 
 
	//判断当前链表中是否包含当前的节点
	private static boolean containgrid(List<Grid> grids, int x, int y) {
		// TODO Auto-generated method stub
		
		for(Grid grid : grids) {
			if((grid.x==x) && (grid.y==y)) {
				return true;
			}
		}
		
		return false;
	}
 
 
	//寻找当前链表中的节点F值 最小的那个节点，并返回这个节点。
	private static Grid findMinGrid(ArrayList<Grid> openlist) {
		// TODO Auto-generated method stub
		
		Grid tempgrid=openlist.get(0);
		for(Grid grid : openlist) {
			if(grid.f<tempgrid.f) {
				tempgrid=grid;
			}
		}
		
		return tempgrid;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int b1=0,b2=0;//起始坐标
		int c1=0,c2=6;
		Grid startgrid=new Grid(b2,b1);
		System.out.println("起点坐标为:"+"("+b1+","+b2+")");
		
		Grid endgrid=new Grid(c2,c1);
		System.out.println("终点坐标为:"+"("+c1+","+c2+")");
		Grid resultgrid=aStarSearch(startgrid,endgrid);
		
		//创建回溯链表
		ArrayList<Grid> path=new ArrayList<Grid>();
		while(resultgrid!=null) {
			path.add(new Grid(resultgrid.x, resultgrid.y));
			resultgrid=resultgrid.parent;
		}
		
		//打印输出当前寻路路径
		int count=0;
		for(int i=0; i<MAZE.length; i++) {
			for(int j=0; j<MAZE[0].length; j++) {
				if(containgrid(path, i, j)) {
					System.out.print("走, ");
					count++;
				}
				else
				{
					System.out.print(MAZE[i][j]+ ", ");
				}
			}
			System.out.println();
			
		}
		System.out.println("最短路径长度为："+count);
	}
}

